# 第2节Dijkstra算法—通过边实现松弛
# 贪心算法
# 邻接矩阵存储图
e = [[0, 0, 0, 0, 0, 0, 0],
     [0, 0, 1, 12, 99, 99, 99],
     [0, 99, 0, 9, 3, 99, 99],
     [0, 99, 99, 0, 99, 5, 99],
     [0, 99, 99, 4, 0, 13, 15],
     [0, 99, 99, 99, 99, 0, 4],
     [0, 99, 99, 99, 99, 99, 0]
     ]

# 初始化dis数组
n = 6  # 顶点个数
m = 9  # 边个数
dis = [0] + [e[1][i] for i in range(1, n + 1)]  # [0]+的作用是使下标对齐到1
print(dis)

# book数组初始化
book = [0 for i in range(0, n + 2)]
print(book)
inf = 99
book[1] = 1
u = 0
# dijkstra算法核心语句
for i in range(1, n):
    # 找到距离1号点最近的点
    min_ = inf
    for j in range(1, n + 1):
        if book[j] == 0 and dis[j] < min_:
            min_ = dis[j]
            u = j
    book[u] = 1
    for k in range(1, n + 1):
        if e[u][k] < inf:  # 代表有边
            if dis[k] > dis[u] + e[u][k]:
                dis[k] = dis[u] + e[u][k]

# 输出最终结果
print(dis)
